The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
XML is a standard for data and documents that is finding wide acceptance in the computer industry. XML describes and provides structure to a body of data, such as a file, a data stream, or a data packet. The specification for XML was developed by the W3C consortium and is located on the Internet at “http://www.w3.org/XML”. According to the XML specification, XML data is organized in nodes that are logically arranged as hierarchical trees. The XML specification also provides for opening and closing tags that delimit different portions of an XML document, which portions are commonly referred to as XML elements. The data included between an opening and a closing tag of an XML element is referred to as the XML element's content. Each XML element may also contain one or more name-value pairs referred to as attributes.
For example, FIG. 1 is a block diagram that illustrates XML document 100, which stores the data of a purchase order. As indicated by opening tag 102, XML document 100 includes the XML element “PurchaseOrder” as the parent node of the document. The “PurchaseOrder” XML element includes the attribute “poid” that is associated with the value “1234”. As indicated by opening tags 104 and 108, the “PurchaseOrder” XML element also includes XML elements “openOrders” and “closedOrders” as child nodes. Each of XML elements “openOrders” and “closedOrders” includes other XML elements as child nodes, such as, for example, XML elements “lineItems” and “itemName”.
The content and structure of an XML document may be validated against an XML schema. As referred to herein, an XML schema is a set of schema components that describes the structure of XML documents and specifies constraints on the content of the documents. Typically, an XML schema conforms to a definition language; examples of such definition languages include, but are not limited to, any type of proprietary or open-source Document Type Definition (DTD) language and the XML Schema Language (as described in the XML Schema Specification, W3C Recommendation 28 Oct. 2004, located at “http://www.w3.org/TR/xmlschema-0/”, “http://www.w3.org/TR/xmlschema-1/”, and “http://www.w3.org/TR/xmlschema-2/”, the entire contents of which are hereby incorporated by reference for all purposes as if fully set forth herein).
Various expression languages have also been developed for accessing and querying a broad spectrum of XML data that is stored in various XML repositories, such as, for example, relational databases, object-relational databases, and object databases. One such language is the XML Path Language (XPath). A specification for XPath is described in “XML Path Language (XPath) 2.0”, W3C Candidate Recommendation 3 Nov. 2005, located at “http://www.w3.org/TR/xpath20/”, the entire content of which is hereby incorporated by reference for all purposes as if fully set forth herein. The basic purpose of XPath is to provide mechanisms for addressing the nodes in XML documents. The basic building block of XPath is the XPath expression, which is a string of characters. XPath provides for different types of XPath expressions that may be constructed from sub-expressions, keywords, symbols, and operands. Evaluating an XPath expression may result in identifying a set of nodes from the input XML documents, one or more atomic values, or more generally, identifying XML data instances of any type allowed by the XQuery Data Model. (A draft specification for the XQuery Data Model is described in “XQuery 1.0 and XPath 2.0 Data Model”, W3C Candidate Recommendation 3 Nov. 2005, located at “http://www.w3.org/TR/xpath-datamode1/”, the entire content of which is hereby incorporated by reference for all purposes as if fully set forth herein.)
One commonly-used type of XPath expression is a location path. A location path, when evaluated, identifies a set of nodes relative to a context node and can be used to locate the nodes within XML document trees. A location path typically includes a series of one or more expressions, which may also be referred to as steps. One type of step, or expression, that may be included in a location path is the axis expression. An axis expression identifies a set of nodes that are reachable from the context node via a specified axis.
One type of axis expression is the descendant axis expression, which may be represented in a location path by the abbreviation “//”. A descendant axis is defined as the transitive closure of the child axis. Thus, a descendant axis expression identifies all descendants of the context node (the children of the context node, the children of the children nodes, and so on), where the descendants do not include attribute nodes and namespace nodes.
Descendant axis expressions are commonly used in queries to query XML documents. For example, consider the following query Q0, which tries to find the purchase order id for all purchase orders stored in XML documents that include a “CPU” item:
Q0.select extractValue(value(v),‘/PurchaseOrder/@poid’)from potab vwhere existsNode(value(v),‘//lineItems[itemName=“CPU”]’)=1
The query Q0 includes the descendant axis expression “//lineItems” as an input argument to the “existsNode” operator. This descendant axis expression may be used in query Q0 for at least the following three reasons, which are also some of the main reasons of why usage of descendant axis expressions in queries is so common:                (1) the user may not be aware of the full XML schema that purchase order XML documents conform to; thus, the user may not be able to list the exact location paths to the “lineItems” XML elements from the root node of a purchase order XML document;        (2) the XML schema, in which the purchase order XML documents are defined, may be allowed to evolve and as a result the location paths to the “lineItems” XML elements may change in the future; thus, using the descendant axis expression “//” in the input argument to the “existsNode” operator protects the user from having to change the query when the XML schema changes; and        (3) there may be multiple paths leading to “lineItems” XML elements from the root; thus, listing all location paths in the query may be too cumbersome for the user.        
Despite the common usage of descendant axis XPath expressions, however, the past approaches for evaluating queries, such as query Q0, that include dependant axis expressions are not efficient and suffer from multiple disadvantages. Specifically, the past approaches are not suited to efficiently handle queries that are based on descendant axis expressions that identify, and are expandable into, multiple location paths.
As an example, consider evaluating query Q0 against the example XML document 100 that is illustrated in FIG. 1. As indicated by opening tags 106 and 110, XML document 110 includes “lineItems” XML elements within both the “openOrders” XML element and the “closedOrders” XML element. Thus, the descendant axis expression “//lineItems” in query Q0 would identify both the “/PurchaseOrder/openOrders/lineItems” location path and the “/PurchaseOrder/closedOrders/lineItems” location path. (It is noted that the XML document in FIG. 1 is provided for illustration purposes only. In a real life scenario, an XML document storing a purchase order may be significantly more complex in structure, may include a significant number of purchase order XML elements, and may include multiple types of XML elements that include “lineItems” XML elements, all of which would make evaluating query Q0 against such an XML document significantly more complex and computationally expensive than XML document 100 in FIG. 1 might otherwise suggest.)
According to one past approach, queries that include operators over descendant axis expressions are not optimized at all. According to this approach, whenever a query engine detects the presence of a descendant axis expression in a query, the query engine first fully materializes the underlying XML documents and only thereafter evaluates the operators that are based on location paths identified by the descendant axis expression. In this way, the query engine ensures that it can properly process the query when the descendant axis expression identifies multiple location paths since the query engine has materialized and can access the entire underlying XML documents. The disadvantage of this approach, however, is that the process of materializing XML documents is computationally expensive with respect to resources, such as, for example, memory, CPU time, and storage space. For this reason, this approach typically suffers from severe performance degradation and user-perceived latency especially in cases where queries are evaluated against large XML documents that are stored in object-relational storage.
According to another past approach, a query engine is generally capable of optimizing query operators over deterministic XPath location paths prior to query execution, but is not capable of processing descendant axis expressions because descendant axis expressions may identify multiple location paths. Thus, in this approach users are required to expressly list all XPath location paths before submitting the query to the query engine. One disadvantage of this approach is that it is not user-friendly and places the burden on the users to know the exact structure of the XML documents being queried, which may not be feasible. Another disadvantage is that the users are not protected from XML schema evolution since queries identifying exact location paths may have to be changed when the XML schema of the queried XML documents is changed.
Although the disadvantages of the above approaches are presented with respect to descendant axis expressions that identify multiple location paths, it is noted that these disadvantages are not unique to the descendant axis expressions. Rather, these disadvantages are common to any kind XPath expression that is capable of identifying multiple location paths. An example of such other XPath expression is the wildcard expression, which may be represented in a principal XPath expression by the symbol “*”. A wildcard expression, when evaluated, identifies all location paths to nodes that are of the same node type as the context node in the principal XPath expression. For example, when used in an XPath expression relative to an element context node, a wild card expression may identify all XML elements that are children nodes of the context node.
Based on the foregoing, techniques are clearly needed for efficiently processing of queries that include operators over XPath expressions that identify multiple location paths.